//
// Created by 党清浩 on 2021/10/27.
//
#include <stdio.h>
#include <malloc.h>

typedef char DataType;
/*定义二叉树*/
typedef struct Node {
    DataType data;
    struct Node *LChild;
    struct Node *RChild;
} BiTNode, *BiTree;

/*扩展先序遍历序列创建二叉链表*/
void CreateBiTree(BiTree *bt);

/*前序遍历*/
void PreOreder(BiTree root);

/*中序遍历*/
void InOrder(BiTree root);

/*后序遍历*/
void PostOrder(BiTree root);

int main() {
    BiTree bt;
    CreateBiTree(&bt);
    printf("\nPreOrder:\n");
    PreOreder(bt);
    printf("\nInOrder:\n");
    InOrder(bt);
    printf("\nPostOrder:\n");
    PostOrder(bt);
    return 0;
}

/*扩展先序遍历序列创建二叉链表*/
void CreateBiTree(BiTree *bt) {
    char ch;
    ch = getchar();
    if (ch == '.') {
        *bt = NULL;
    } else {
        *bt = (BiTree) malloc(sizeof(BiTree));
        (*bt)->data = ch;
        CreateBiTree(&((*bt)->LChild));
        CreateBiTree(&((*bt)->RChild));
    }
}

void PreOreder(BiTree root) {
    if (root != NULL) {
        printf("%-3c", root->data);
        PreOreder(root->LChild);
        PreOreder(root->RChild);
    }
}

void InOrder(BiTree root) {
    if (root != NULL) {
        InOrder(root->LChild);
        printf("%-3c", root->data);
        InOrder(root->RChild);
    }
}

void PostOrder(BiTree root) {
    if (root != NULL) {
        PostOrder(root->LChild);
        PostOrder(root->RChild);
        printf("%-3c", root->data);
    }
}
